#include <stdio.h>
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
void dump( ListNode *head ) {
    ListNode *p = head;
    while(p) {
        cout << p->val << endl;
        p = p->next;
    }
}

class Solution {
    public:
        void reorderList(ListNode* head) {

            if (!head
                    || !head->next
                    || !head->next->next) {
                return ;
            }

            int len = 0;
            ListNode *p = head, *q = head;
            while(p && p->next) {
                q = q->next;
                p = p->next->next;
            }

            ListNode *tmp = head;
            while(tmp->next != q) {
                tmp = tmp->next;
            }
            tmp->next = NULL;

            ListNode *tail = NULL;
            if (p) {
                // odd len
                tail = q;
                q = q->next;
                tail->next = NULL;
            }

            ListNode *rq = reverse(q);
            merge(head, rq, tail);
        }

        ListNode *reverse(ListNode *head) {

            if (!head) {
                return head;
            }

            ListNode *prev = NULL;
            ListNode *p = head;
            while(p) {
                ListNode *tmp = p->next;
                p->next = prev;
                prev = p;
                p = tmp;
            }

            return prev;
        }

        ListNode *merge(ListNode *l1, ListNode *l2, ListNode *tail) {
            ListNode *head = NULL, *prev = NULL;

            while(l1 && l2) {

                if (!head) {
                    head = l1;
                }

                ListNode *tmp1 = l1->next;
                ListNode *tmp2 = l2->next;

                l1->next = l2;
                l2->next = tmp1;
                l1 = tmp1;
                l2 = tmp2;
            }

            if (tail) {
                ListNode *p = head;
                while(p->next) {
                    p = p->next;
                }
                p->next =tail;
                tail->next = NULL;
            }
            return head;
        }
};


int main() {

    vector<int> v = {1,2,3,4};

    ListNode *head = NULL;
    ListNode *p = NULL;

    for (auto i:v) {
        if (!head) {
            head = new ListNode(i);
            p = head;
        } else {
            p->next = new ListNode(i);
            p = p->next;
        }
    }

    Solution s;
    s.reorderList(head);
    dump(head);
}
